翻訳と辞書 Words near each other ・ Fáelán mac Murchado ・ Fáfnismál ・ Fáider Burbano ・ Fáilbe mac Pípáin ・ Fáilte ・ Fáilte Ireland ・ Fáilte Towers ・ Fáinne ・ Fáj ・ Fálkar (soundtrack) ・ Fálkinn ・ Fámjin ・ Fámjin stone ・ Fánk ・ Fárbauti ・ Fáry's theorem ・ FÁS expenses scandal ・ Fáskrúðsfjarðargöng ・ Fáskrúðsfjörður ・ Fáskrúðsfjörður Airport ・ Fátima (Buenos Aires Premetro) ・ Fátima Aburto Baselga ・ Fátima Bernardes ・ Fátima Blázquez ・ Fátima Báñez ・ Fátima Campos Ferreira ・ Fátima Choi ・ Fátima do Sul ・ Fátima Felgueiras ・ Fátima Ferreira Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Fáry's theorem ： ウィキペディア英語版 Fáry's theorem In mathematics, Fáry's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by , , and . == Proof == One way of proving Fáry's theorem is to use mathematical induction.〔The proof that follows can be found in .〕 Let be a simple planar graph with vertices; we may add edges if necessary so that is maximal planar. All faces of will be triangles, as we could add an edge into any face with more sides while preserving planarity, contradicting the assumption of maximal planarity. Choose some three vertices forming a triangular face of . We prove by induction on that there exists a straight-line embedding of in which triangle is the outer face of the embedding. As a base case, the result is trivial when and , and are the only vertices in . Otherwise, all vertices in have at least three neighbors. By Euler's formula for planar graphs, has edges; equivalently, if one defines the ''deficiency'' of a vertex in to be , the sum of the deficiencies is . Each vertex in can have deficiency at most three, so there are at least four vertices with positive deficiency. In particular we can choose a vertex with at most five neighbors that is different from , and . Let be formed by removing from and retriangulating the face formed by removing . By induction, has a straight line embedding in which is the outer face. Remove the added edges in , forming a polygon with at most five sides into which should be placed to complete the drawing. By the Art gallery theorem, there exists a point interior to at which can be placed so that the edges from to the vertices of do not cross any other edges, completing the proof. The induction step of this proof is illustrated at right. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fáry's theorem」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.